1.1 Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
In [43]:
# from IPython.core.debugger import set_trace
def has_unique_characters(str=''):
'''
Checks if a string has all unique characters
>>> has_unique_characters('abc')
True
>>> has_unique_characters()
True
>>> has_unique_characters('abac')
False
'''
# 1/ time: 1.74 µs ± 14.5 ns ---------------------------
# unique_chars = dict.fromkeys(str,1)
# return len(unique_chars)==len(str)
# 2/ time: 1.04 µs ± 7.39 ns using dictionary ----------
# unique_chars ={}
# for char in str:
# if char in unique_chars:
# return False
# unique_chars[char]=1
# return True
# 3/ 1.4 µs ± 19.1 ns using a set -----------------------
# char_set =set()
# for char in str:
# if char in char_set:
# return False
# char_set.add(char)
# return True
# 4/ 3.16 µs ± 131 ns using a bit vector ----------------
# bit_vector =0b0
# pos_a=ord('a')
# import pdb; pdb.set_trace()
# for char in str:
# pos_char=ord(char)-pos_a
# if bit_vector & (1 << pos_char):
# return False
# bit_vector |= (1 << pos_char)
# return True
# 5/ 1.88 µs ± 12.2 ns Array -----------------------------
a =[0]*40
pos_a=ord('a')
# import pdb; pdb.set_trace()
for char in str:
pos_char=ord(char)-pos_a
if a[pos_char]:
return False
a[pos_char] =1
return True
# print(has_unique_characters('qwertyuuidfsdgsg'))
%timeit has_unique_characters('qwertyuuidfsdgsg')
# import doctest; doctest.testmod()
1.2 Check Permutation: Given two strings,write a method to decide if one is a permutation of the other.
In [37]:
# def isPermutations(s1,s2):
# len1 = len(s1)
# len2 = len(s2)
# if len1 != len2:
# return False
# ss1=sorted(s1)
# ss2=sorted(s2)
# for i in range(0,len1):
# if ss1[i] != ss2[i]:
# return False
# return True
def isPermutations(s1,s2):
if len(s1) != len(s2):
return False
char_counts={}
# fill it
for c in s1:
char_counts[c] = char_counts.get(c,0) +1
# empty it
for c in s2:
char_counts[c] = char_counts.get(c,0) -1
# check if all are 0
for c in char_counts:
if char_counts[c] != 0:
return False
return True
print( isPermutations('abcdefffgh', 'dcabefghff') )
Write a method to replace all spaces in a string with '%20 You may assume that the string has suf cient space at the end to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)
| EXAMPLE | |
|---|---|
| Input: | "Mr John Smith ", 13 |
| Output: | "Mr%20John%20Smith" |
In [94]:
def urlify(ss="Mr John Smith ", true_len=13):
# 574 ns ± 47.7 ns
# return s.strip().replace(' ','%20')
# 760 ns ± 34 ns
# return '%20'.join(s.strip().split(' '))
# 6.54 µs ± 191 ns
# n_spaces = ss.count(' ',0,true_len)
n_spaces = 0
for i in range(0,true_len):
if ss[i]==' ':
n_spaces +=1
s=list(ss)
for i in range(true_len-1,0,-1):
if s[i] != ' ':
s[i+n_spaces*2]=s[i]
else:
s[i+n_spaces*2]='0'
s[i+n_spaces*2-1]='2'
s[i+n_spaces*2-2]='%'
n_spaces -= 1
return ''.join(s)
urlify()=="Mr%20John%20Smith"
# %timeit urlify()
Out[94]:
There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.
pale, ple -> true
pales, pale -> true
pale, bale -> true
pale, bake -> false1h
In [19]:
def first_diff(old, new):
for i in range(0, min( len(old), len(new) )):
if old[i] != new[i]:
return i
return i+1
def inserted1(old, new):
if len(new)-len(old)!=1:
return False
i = first_diff(old,new)
if old[i:] == new[i+1:]:
return True
return False
return True
def deleted1(old, new):
if len(new)-len(old)!=-1:
return False
i = first_diff(old,new)
if old[i+1:] == new[i:]:
return True
return False
return True
def updated1(old, new):
if len(new)-len(old)!=0:
return False
i = first_diff(old,new)
if old[i+1:] == new[i+1:]:
return True
return False
def zero_or_one(old, new):
# if old == new :
# return True
# if inserted1(old,new) \
# or updated1(old,new) \
# or deleted1(old,new):
# return True
# return False
# len_diff = len(new)-len(old)
# checks = {0:updated1, 1:inserted1, -1:deleted1}
# return checks.get(len_diff, lambda o,n: False)(old,new)
len_diff = len(new)-len(old)
if len_diff == 0: return updated1(old,new)
elif len_diff ==1: return inserted1(old,new)
elif len_diff == -1: return deleted1(old,new)
else: return False
print (True, zero_or_one('pale', 'pale'))
print (True, zero_or_one('pale', 'ple'))
print (True, zero_or_one('pales', 'pale'))
print (True, zero_or_one('pale', 'bale'))
print (False,zero_or_one('pale', 'bake'))
"""
>>> zero_or_one('pale', 'pale')
True
>>> zero_or_one('pale', 'ple')
True
>>> zero_or_one('pales', 'pale')
True
>>> zero_or_one('pale', 'bale')
True
>>> zero_or_one('pale', 'bake')
False
"""
import doctest; doctest.testmod()
Out[19]:
Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).
In [12]:
char=''
count=0
def compr(c):
global char,count
if char == c:
count+=1
return ''
old_char, old_count = char, count
char, count = c, 1
if old_count>0:
return '{}{}'.format(old_char,old_count)
return ''
def compress(string):
s=''
for c in string:
s+=compr(c)
s+=compr('')
return string if len(string) <= len(s) else s
print(compress('xaaabbcdddd eee '))
print(compress('xaa'))
In [79]:
N = 3
m = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
def generate_m(N):
'''Generates a square matrix NxN'''
k = 1
m = []
for i in range(0, N):
n = []
m.append(n)
for j in range(0, N):
n.append(k)
k += 1
return m
def print_m(m, N):
"Pretty prints matrix"
for i in range(0, N):
for j in range(0, N):
print('{0:>4d}'.format(m[i][j]), end='')
print()
print()
def rotate(l, n):
'''Rotates list to the right'''
return l[n:]+l[:n]
def rotate_m(m, N):
for i in range(0, N//2+N % 2):
for j in range(0, N//2):
cp = [m[i][j], m[N-j-1][i], m[N-i-1][N-j-1], m[j][N-i-1]].copy()
[m[i][j], m[N-j-1][i], m[N-i-1][N-j-1],
m[j][N-i-1]] = rotate(cp, 1)
N = 5
m = generate_m(N)
print_m(m, N)
print('rotated:')
rotate_m(m, N)
print_m(m, N)
[x for x in dir() if not x.startswith('__')]